package everydayone.gcdofstring;
/**
 * @Date 2020/03/12
 * @author 王光浩
 * @Thinking 使用辗转相除法，找出最大公约长度，然后在任意一个字符串的后面截取，判断该子字符串是否是我们要找的
 * @         如果不是，则返回false。
 * @Analysis 时间复杂度O（n），空间复杂度O（n），计算两个数的最大公约数需要O（logn）
 */
public class MyMethodOne {
	public String gcdOfStrings(String str1, String str2) {
		int len1=str1.length()>str2.length()?str1.length():str2.length();
		int len2=str1.length()>str2.length()?str2.length():str1.length();
		if(len1==len2) {
			if(str1.equals(str2))
				return str1;
			return "";
		}
		//求最大公因子，获取最长公共子字符串
		while(len1%len2!=0) {
			len1=(len1%len2)^len2;
			len2=len1^len2;
			len1=len1^len2;
		}
		String res=str1.substring(str1.length()-len2);
		//判断该子字符串是否和要求
		StringBuilder test=new StringBuilder();
		int count=str1.length()/res.length();
		for(int i=0;i<count;i++)
			test.append(res);
		if(!test.toString().equals(str1))
			return "";
		test.setLength(0);
		count=str2.length()/res.length();
		for(int i=0;i<count;i++)
			test.append(res);
		if(!test.toString().equals(str2))
			return "";
		return res;
    }
}
